import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 东莞呵呵
 * Date:2022-06-23
 * Time:15:24
 */
public class RadixSort {
    public static void radixSort(int[] array) {
        //创建十个桶（队列）
        List<Queue<Integer>> queueList = new ArrayList<>(10);
        for (int i = 0; i < 10; i++) {
            queueList.add(new ArrayBlockingQueue<Integer>(1000));
        }
        //找出数组中的最大值
        int max = array[0];
        for (int k : array) {
            if (max < k) {
                max = k;
            }
        }
        //记录最大值的位数
        int count = 0;
        while (max != 0) {
            count++;
            max /= 10;
        }
        //开始排序
        //x代表当前的基数位
        int x = 0;
        while (x < count) {
            for (int i = 0; i < array.length; i++) {
                int num = getFigure(array[i], x);
                queueList.get(num).offer(array[i]);
            }
            int j = 0;
            for (int i = 0; i < array.length; i++) {

                if (j <= 9 && queueList.get(j).isEmpty()) {
                    j++;
                    //因为当前队列为空时，需要跳过这次循环后i++，但是此时i处的array[i]没有赋值，所以要i--
                    i--;
                    continue;
                }
                array[i] = queueList.get(j).poll();
            }
            x++;
        }
    }

    /**
     * 返回第k位的值是几（k=0，1，2）（个，十，百）
     * @param i
     * @param k
     * @return
     */
    public static int getFigure(int i, int k) {
        int arr[] = {1, 10, 100, 1000, 10000, 100000, 1000000};
        return (i / arr[k]) % 10;
    }

    public static void main(String[] args) {
        int[] arr = {65, 43, 5, 7, 4, 5, 76, 23, 4, 765, 42, 6, 7, 8};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
